import java.io.File;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
/*
 * Amos Kittelson 
 * COP3503 - Computer Science 2
 * Assignment 3 - Railroad Building
 * Due 6 July 2010 (Extended due to military duty)
 */

/*

	Execution Points (30 pts)
		Use the 6 sample cases worth 5 points each in the attached file. If all cases return a correct 
		MST but not in the proper order, then deduct 5 points from them out of 30. 
		If only one or two cases have the correct MST but not in the proper order, then deduct 2 or 4 points, 
		respectively. If a case does not have the correct MST weight, then it's automatically worth 0 points.
*/


public class Railroad {
	
	public static void main(String[] args) {

		boolean debug = false;
				
		Heap heap;
		
		try{
			
			String file = "railroad.in";
			
			//Open file
			Scanner fin = new Scanner(new File(file));
			
			//Scan first int from .txt file. Gives the number of cases/scenarios
			//in the .txt file
			int num_cases = Integer.parseInt(fin.nextLine());
			if (debug) System.out.println("Test Cases:" + num_cases);
			
			//For loop to iterate through all cases
			for(int i=0; i<num_cases; i++){
		


				// The next line in input file is the number of tracks to read in
				int tracks = fin.nextInt();
				
				// Create the new graph and the heap to store Edges in
				Graph g = new Graph();
				// heap = new Heap(tracks);
				
				// Loop through all the tracks in the test case
				for (int trackCnt = 1; trackCnt <= tracks; trackCnt++){
				
					// The line in the input file is:
					// City City Cost
					// Create new Vertex's for the Cities
					// and a new Edge with the two new Vertex's as
					// its start and end points
					Vertex start = new Vertex(fin.next());
					Vertex end = new Vertex(fin.next());
					Edge edge = new Edge(start, end, fin.nextInt(), trackCnt);
					
					// Since this is an undirected graph we can sorts the
					// start and end vertices alphebetically as specified 
					// in the requirements.
					edge.sort();
					
					// Add the Vertices and Edges to the Graph. The Graph
					// does not allow duplicate Vertices and automatically
					// finds duplicates in the add method
					g.addVertex(start);
					g.addVertex(end);
					g.addEdge(edge);
					
	
					
				} // for loop for all tracks
				
				// Take all the edges in the graph and add them to the
				// heap
				/*
				for (int j = 0; j < g.sizeOf(); j++){
					if (debug) prt (g.getEdge(j).toString());
					heap.add(g.getEdge(j));
				}
				*/
				
				heap = new Heap(g);
				
				//Edge[] edgeArray = new Edge[g.sizeOf()];
				//ArrayList<Edge> edgeList;
				//edgeList = g.returnArray();
				//edgeArray = (Edge[]) edgeList.toArray();
				
				
				
				
				// heap = new Heap(edgeArray);
				
				
				// Pass the Edges in the Heap to the Kruskal algorithm
				// to create the set of the minimal edges required to
				// connect all Vertices
				DisjointSet minCost = Kruskal (heap, tracks);
				
				// At this point minCost is sorted by edge cost but 
				// it needs to be resorted alphabetically and the
				// total cost tallied for display.
				
				PriorityQueue<Edge> pq = new PriorityQueue<Edge>(tracks, 
						new Comparator<Edge>(){
							// Override the Edge compare method
							public int compare(Edge a, Edge b){
								String starta = a.getStart().getLabel();
								String startb = b.getStart().getLabel();
								
								// If the starting lables are the same then
								// sort by the ending labels
								if (starta.equals(startb))
								{
									starta = a.getEnd().getLabel();
									startb = b.getEnd().getLabel();
									return starta.compareTo(startb);
								}
								else
									return starta.compareTo(startb);
							}
					} // EndCompare override		
				); // pq
				
				int minimumCost = 0;
				
				// This loop moves the alphabetically unsorted Graph 
				// into a sorted array and adds up the total cost
				for (int cnt = 1; cnt < minCost.getSize(); cnt++){
					if (minCost.getElement(cnt) != null){
						minimumCost += minCost.getElement(cnt).getWeight();
					pq.add(minCost.getElement(cnt));
					}
				}
				
				prt("The minimum cost of the railway system is " + minimumCost);
				
				while (!pq.isEmpty())
					System.out.println(pq.poll());
				
				prt("");
				
			} // for loop for all cases in the file
			
		}
		catch (Exception e)
		{
			prt(e.toString());
		}
		
		
	} // main()

	// Method to read in the data from the next line
	public static void getNextLine(Scanner fin, String start, String end, int cost){
		start = fin.next();
		end = fin.next();
		cost = fin.nextInt();
	}
	
	// Method for quick and dirty test output
	public static void prt(String s){
			System.out.println(s);	
	}
	
	// Print the track nicely
	public static void prtTrack(String start, String end, int cost){
		prt("start:" + start + " end:" + end + " cost:" + cost);
	}
	
	public static DisjointSet Kruskal(Heap heap, int size){
		
		/*
		 * Let V = {an empty set}
		 * For i=1 to n-1, (where there are n vertices in a graph)
		 * 	V = Union(V, e) where e is the edge with the minimum edge
		 * 					weight not already in V, and that does NOT
		 * 					form a cycle when added to V.
		 * Return V
		 */
		
		boolean debug = false;
		
		// Create the new set (V). 
		// Indices in the graph start at one.
		DisjointSet ds = new DisjointSet(size + 1);	
		
		// Process all the edges in the heap
		for (int i = 1; i < size; i++){
			Edge edge = new Edge((Edge)heap.deleteMin());
			
			if (debug) prt ("Kruskal: Popped " + edge + " from the heap");
			
			// check to see if the edge start and end Vertex's are
			// already in the set. If they are then adding it would
			// create a cycle, so don't add it. Otherwise, do a
			// union of the Edges
			if (ds.Find(edge.getStart()) == -1 || ds.Find(edge.getEnd()) == -1 ){
				if (debug) prt ("Kruskal: Edge Vertex's not in set");
				
				// If the Disjoint set is empty then add the first element
				// Otherwise 
				if (ds.getElement(0) == null)			
					ds.addElement(edge);
				else
					// Since we're not keeping track of what connects to
					// what, just add the edge to the set.
					ds.Union(ds.getElement(0), edge);				
		
				}
				else
					if (debug) prt ("Kruskal: and it DID make a cycle");
			}
		
		// Return the set from Kruskal's algorithm
		return ds;
		
	} // Krustals' Algorithm
	
} // class Railroad

